1
Vượt qua các ràng buộc cứng nhắc: Khung Lagrange
MATH008Lesson 5
00:00
Trong thế giới tối ưu thông thường, một ràng buộc giống như một bức tường nhị phân: bạn hoặc nằm trong vùng khả thi, hoặc nằm ngoài. Tuy nhiên, trong các hệ thống phức tạp, những ràng buộc "cứng" này có thể trở nên rập khuôn về mặt toán học. Khung Lagrange cung cấp nền tảng để vượt qua điều đó, biến các ràng buộc thành các hàm mục tiêu được mở rộng (augmented), trong đó các vi phạm được tính vào dưới dạng hình phạt có trọng số. Điều này không đơn thuần là một thủ thuật; nó là nền tảng để định lượng "chi phí" của các ràng buộc thông qua các thừa số Lagrange.

1. Từ các ràng buộc cứng nhắc đến các hình phạt mềm mại

Xét một bài toán chuẩn: tối thiểu hóa $f_0(x)$ với điều kiện $f_i(x) \le 0$ và $h_i(x) = 0$. Một ràng buộc "cứng" tương đương với một hàm chỉ thị:

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

Phương pháp Lagrange thay thế bước nhảy vô hạn này bằng một hình phạt tuyến tính. Chúng ta bổ sung hàm mục tiêu bằng tổng có trọng số của các hàm ràng buộc:

$$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)$$

Ở đây, $\lambda_i$ là thừa số Lagrange. Nó hoạt động như một hình phạt "mềm", điều chỉnh mức độ ảnh hưởng của bất đẳng thức thứ $i$. Quan trọng là, chúng ta chưa giả định tính lồi; khung này mang tính phổ quát.

Quan điểm đối ngẫu

Chúng ta định nghĩa hàm đối ngẫu Lagrange $g(\lambda, \nu)$ là cận dưới đúng của hàm Lagrange theo biến $x$. Một tính chất then chốt là tính chất giới hạn dưới: với mọi $\lambda \succeq 0$, $g(\lambda, \nu) \le p^*$. Điều này cho phép chúng ta xác định giới hạn trên giá trị tối ưu của các bài toán mà nếu không thì có thể không thể giải trực tiếp.

2. Trường hợp nghiên cứu: Điều khiển xe lai

Hãy tưởng tượng một chiếc xe cân bằng giữa tiêu thụ nhiên liệu và tuổi thọ pin. Các ràng buộc là vật lý: nhu cầu công suất phải được đáp ứng tại mọi thời điểm.

  • Cân bằng công suất: $P_{\text{req}}(t) = p_{\text{eng}}(t) + p_{\text{mg}}(t) - p_{\text{br}}(t)$
  • Dynamics pin: $E(t+1) = E(t) - p_{\text{mg}}(t) - \eta |p_{\text{mg}}(t)|$
  • Mục tiêu: Tối thiểu hóa $F_{\text{total}} = \sum_{t=1}^{T} F(p_{\text{eng}}(t))$

Bằng cách áp dụng khung Lagrange, các ràng buộc về dung lượng pin được chuyển đổi thành giá bóng. Bộ điều khiển quyết định đốt nhiên liệu hay sử dụng pin dựa trên "chi phí" hiện tại của năng lượng (thừa số) so với chi phí nhiên liệu.

🎯 Nguyên tắc cốt lõi: Đối ngẫu và khả thi
Tính chất giới hạn dưới $p^* \in [g(\lambda, \nu), f_0(x)]$ chỉ thực sự có ý nghĩa khi $\lambda \succeq 0$ và $g(\lambda, \nu) > -\infty$. Mối quan hệ này vẫn đúng ngay cả trong các trường hợp không lồi, mặc dù có thể xuất hiện khoảng trống đối ngẫu ("duality gap").